//
// Created by Tan Ke on 2023/12/15.
//

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>


struct RecordItem {
    int maxMod0;
    int maxMod1;
    int maxMod2;
};

int maxSumDivThree(int* nums, int numsSize)
{
    struct RecordItem* recordItemList = (struct RecordItem*) malloc(sizeof(struct RecordItem) * numsSize);

    recordItemList[0].maxMod0 = 0;
    recordItemList[0].maxMod1 = 0;
    recordItemList[0].maxMod2 = 0;

    if (nums[0] % 3 == 0) {
        recordItemList[0].maxMod0 = nums[0];
    } else if (nums[0] % 3 == 1) {
        recordItemList[0].maxMod1 = nums[0];
    } else {
        recordItemList[0].maxMod2 = nums[0];
    }

    for (int i = 1; i < numsSize; i ++) {
        recordItemList[i].maxMod0 = recordItemList[i-1].maxMod0;
        recordItemList[i].maxMod1 = recordItemList[i-1].maxMod1;
        recordItemList[i].maxMod2 = recordItemList[i-1].maxMod2;

        if (nums[i] % 3 == 0) {
            recordItemList[i].maxMod0 += nums[i];
            if (recordItemList[i].maxMod1 > 0) {
                recordItemList[i].maxMod1 += nums[i];
            }
            if (recordItemList[i].maxMod2 > 0) {
                recordItemList[i].maxMod2 += nums[i];
            }
        } else if (nums[i] % 3 == 1) {
            if (recordItemList[i-1].maxMod2 > 0 && recordItemList[i-1].maxMod2 + nums[i] > recordItemList[i].maxMod0) {
                recordItemList[i].maxMod0 = recordItemList[i-1].maxMod2 + nums[i];
            }
            if (recordItemList[i-1].maxMod0 + nums[i] > recordItemList[i].maxMod1) {
                recordItemList[i].maxMod1 = recordItemList[i-1].maxMod0 + nums[i];
            }
            if (recordItemList[i-1].maxMod1 > 0 && recordItemList[i-1].maxMod1 + nums[i] > recordItemList[i].maxMod2) {
                recordItemList[i].maxMod2 = recordItemList[i-1].maxMod1 + nums[i];
            }
        } else if (nums[i] % 3 == 2) {
            if (recordItemList[i-1].maxMod1 > 0 && recordItemList[i-1].maxMod1 + nums[i] > recordItemList[i].maxMod0) {
                recordItemList[i].maxMod0 = recordItemList[i-1].maxMod1 + nums[i];
            }
            if (recordItemList[i-1].maxMod2 > 0 && recordItemList[i-1].maxMod2 + nums[i] > recordItemList[i].maxMod1) {
                recordItemList[i].maxMod1 = recordItemList[i-1].maxMod2 + nums[i];
            }
            if (recordItemList[i-1].maxMod0 + nums[i] > recordItemList[i].maxMod2) {
                recordItemList[i].maxMod2 = recordItemList[i-1].maxMod0 + nums[i];
            }
        }
    }
#if 0
    for (int i = 0; i < numsSize; i ++) {
        printf(" %d, %d, %d \n", recordItemList[i].maxMod0, recordItemList[i].maxMod1, recordItemList[i].maxMod2);
    }
#endif

    return recordItemList[numsSize-1].maxMod0;
}

int main(void)
{
    int nums[5] = {3, 6, 5, 1, 8};
    printf("%d\n", maxSumDivThree(nums, 5));

    int nums1[1] = {4};
    printf("%d\n", maxSumDivThree(nums1, 1));

    int nums2[5] = {1, 2, 3, 4, 4};
    printf("%d\n", maxSumDivThree(nums2, 5));
    return 0;
}

